#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node_s {
	char data;
	struct node_s *left;
	struct node_s *right;
} node_t;

void pre_scan_tree(node_t *node)
{
	printf("%c\t", node->data);
	if (node->left)
		pre_scan_tree(node->left);
	if(node->right)
		pre_scan_tree(node->right);
}

void mid_scan_tree(node_t *node)
{
	if (node->left)
		mid_scan_tree(node->left);
	printf("%c\t", node->data);
	if(node->right)
		mid_scan_tree(node->right);
}

int find_left_len(char str[], char parent)
{
	int i;
	
	for (i=0; str[i] != parent; i++);

	return i;
}

void build_tree(node_t **root, char pre[], char mid[], int len)
{
	int left_len = 0, right_len;
	node_t *new = (node_t *)malloc(sizeof(node_t));

	memset(new, 0, sizeof(node_t));
	new->data = pre[0];
	new->left = NULL;
	new->right = NULL;
	*root = new;

	if (len == 1)
		return;
	
	left_len = find_left_len(mid, new->data);
	right_len = len - left_len - 1;	

	if (left_len) {
		build_tree(&new->left, pre + 1, mid, left_len);
	}
	if (right_len) {
		build_tree(&new->right, pre + left_len + 1, mid + left_len + 1, right_len);
	}
}

int main()
{
	node_t *root;

	char *p = "abdcef";
	char *m = "dbacef";

	build_tree(&root, p, m, strlen(p));

	printf("\n");
	pre_scan_tree(root);
	printf("\n");
	mid_scan_tree(root);
	printf("\n");

	return 0;
}

